|
In theoretical computer science, a ''transition system'' is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a singleton, the system is essentially unlabeled, and a simpler definition that omits the labels is possible. Transition systems coincide mathematically with abstract rewriting systems (as explained further in this article) and directed graphs. They differ from finite state automata in several ways: * The set of states is not necessarily finite, or even countable. * The set of transitions is not necessarily finite, or even countable. * No "start" state or "final" states are given. Transition systems can be represented as directed graphs. == Formal definition == Formally, a transition system is a pair (''S'', →) where ''S'' is a set of states and → is a set of state transitions (i.e., a subset of ''S'' × ''S''). The fact that there is a transition from state ''p'' to state ''q'', i.e. (''p'', ''q'') ∈ →, is written as ''p'' → ''q''. A labelled transition system is a tuple (''S'', Λ, →) where ''S'' is a set of states, Λ is a set of labels and → is a set of labelled transitions (i.e., a subset of ''S'' × Λ × ''S''). The fact that (''p'',α,''q'') ∈ → is written as : This represents the fact that there is a transition from state ''p'' to state ''q'' with label α. Labels can represent different things depending on the language of interest. Typical uses of labels include representing input expected, conditions that must be true to trigger the transition, or actions performed during the transition. Labelled transitions systems were originally introduced as ''named'' transition systems.〔Robert M. Keller (July 1976) "Formal Verification of Parallel Programs", ''Communications of the ACM'', vol 19, nr ''7'', p. 371-384.〕 If, for any given ''p'' and α, there exists only a single tuple (''p'',α,''q'') in →, then one says that α is ''deterministic'' (for ''p''). If, for any given ''p'' and α, there exists at least one tuple (''p'',α,''q'') in →, then one says that α is ''executable'' (for ''p''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Transition system」の詳細全文を読む スポンサード リンク
|